//给定两个整数，分别表示分数的分子 numerator 和分母 denominator，以 字符串形式返回小数 。 
//
// 如果小数部分为循环小数，则将循环的部分括在括号内。 
//
// 如果存在多个答案，只需返回 任意一个 。 
//
// 对于所有给定的输入，保证 答案字符串的长度小于 10⁴ 。 
//
// 
//
// 示例 1： 
//
// 
//输入：numerator = 1, denominator = 2
//输出："0.5"
// 
//
// 示例 2： 
//
// 
//输入：numerator = 2, denominator = 1
//输出："2"
// 
//
// 示例 3： 
//
// 
//输入：numerator = 4, denominator = 333
//输出："0.(012)"
// 
//
// 
//
// 提示： 
//
// 
// -2³¹ <= numerator, denominator <= 2³¹ - 1 
// denominator != 0 
// 
//
// Related Topics 哈希表 数学 字符串 👍 532 👎 0


package LeetCode.editor.cn;


import java.util.HashMap;
import java.util.Map;

/**
 * @author ldltd
 * @date 2025-09-24 14:33:12
 * @description 166.分数到小数
 
 */
 
public class FractionToRecurringDecimal {
    public static void main(String[] args) {
    //测试代码
    FractionToRecurringDecimal fun = new FractionToRecurringDecimal();
    Solution solution= fun.new Solution();
    
    }

//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
        /*
1.符号处理
直接判断正负，然后把分子分母取绝对值
2.整数处理
整数部分直接相除
3.小数处理
长除法：每次将余数乘以 10，再除以分母，得到新的商和余数。
循环检测：当某次计算的余数在之前出现过，说明从上次出现这个余数到当前这一段小数是循环节。
可以用哈希表记录每个余数第一次出现的位置，以便插入括号。
        * */
    public String fractionToDecimal(int numerator, int denominator) {
        // 处理符号
        int sign = (numerator > 0) ^ (denominator > 0) ? -1 : 1;
        StringBuilder sb = new StringBuilder();
        // 处理整数部分
        long num = Math.abs((long) numerator);
        long den = Math.abs((long) denominator);
        if (sign == -1 && num != 0) {
            sb.append("-");
        }
        // 整数部分
        sb.append(num / den);
        // 处理小数部分
        long remainder = num % den;
        // 没有小数部分 直接返回
        if (remainder == 0) {
            return sb.toString();
        }
        sb.append(".");
        // 用哈希表记录余数及其对应的小数部分位置
        //无限小数：
        //纯循环小数：从小数点后第一位就开始循环（分母与 10 互质）。
        //混循环小数：小数点后有不循环的部分，然后进入循环部分。
        Map<Long, Integer> map = new HashMap<>();
        while (remainder != 0) {
            // 如果余数出现过，说明进入循环节
            if (map.containsKey(remainder)) {
                // 取出循环节的起始位置
                int index = map.get(remainder);
                // 插入括号
                sb.insert(index, "(");
                sb.append(")");
                break;
            }
            // 记录余数及其对应的小数部分位置
            map.put(remainder, sb.length());
            remainder *= 10;
            sb.append(remainder / den);
            remainder %= den;
        }
        return sb.toString();
    }
}
//leetcode submit region end(Prohibit modification and deletion)

}
